package a10_动态规划;

/**
 * <p>
 * a23_零钱兑换
 * </p>
 *
 * @author flyduck
 * @since 2025/2/17
 */
public class a23_零钱兑换 {
    //装满背包的最小数量

    //dp[j]:装满容量为j背包的最少物品为dp[j]
    //最终求：dp[amount]

    //递推：dp[j] = Math.min(dp[j],dp[j - coins[i]] + 1);

    //但是如果dp[0] = 0，那么结果肯定为0

    public int coinChange(int[] coins, int amount) {

            int[] dp = new int[amount+1];
            for (int i = 0; i < dp.length; i++) {
                dp[i] = Integer.MAX_VALUE;
            }
            dp[0] = 0;


            for (int i = 0; i < coins.length; i++) {
                for (int j = coins[i]; j <= amount; j++) {
                    if(j > coins[i] && dp[j - coins[i]] != Integer.MAX_VALUE){
                        dp[j] = Math.min(dp[j],dp[j - coins[i]] + 1);
                    }
                }
            }

            return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}
